package main.java.indi.zyj.c150.dp;

public class _02_package {


    static int[] weight = {0, 2, 3, 4, 5};
    static int[] value = {0, 3, 4, 5, 6};
    static int[][] dp = new int[5][9];
    static int[] object = new int[5];



    public static void Dynamic(){
        for (int i = 1; i < 5; i++) {
            for (int j = 1; j < 9; j++) {
                if (weight[i] > j){
                    dp[i][j] = dp[i - 1][j];
                }else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
                }
            }
        }
    }

    //   回溯去找那些放入背包了
    public static void Find(int i, int j){
        if (i == 0){     //
            for (int k = 0; k < 5; k++) {
                System.out.println(object[k]);
            }
            return;
        }
        if (dp[i][j] == dp[i -1][j]){
            object[i] = 0;  //  未放入
            Find(i-1, j);
        }else if (dp[i][j] == (dp[i - 1][j - weight[i]] + value[i])){
            object[i] = 1;  //  已放入
            Find(i-1, j - weight[i]);
        }
    }


    public static void main(String[] args) {

        dp[0][0] = 0;
        Dynamic();
        Find(4, 8);

    }
}
